/*
 * @lc app=leetcode.cn id=86 lang=cpp
 *
 * [86] 分隔链表
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution
{
public:
  ListNode* partition(ListNode* head, int x)
  {
    ListNode* less = new ListNode(INT_MIN);
    ListNode* greater = new ListNode(INT_MIN);
    ListNode* less_tail = less, *greater_tail = greater;

    for (; head != nullptr; head = head->next) {
      if (head->val < x) {
        less_tail->next = head;
        less_tail = head;
      }
      else {
        greater_tail->next = head;
        greater_tail = head;
      }
    }

    greater_tail->next = nullptr;
    less_tail->next = greater->next;
    return less->next;
  }
};
// @lc code=end
